package com.heima.leetcode.algorithm.sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

/**
 * <strong>用线性时间复杂度排序数组并求出最大间隙</strong>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/7 10:10
 */
public class MaximumGap {

    /**
     * <h3>方法一：只用桶排序</h3>
     * 会超出内存限制，因为，测试中数组很大，创建的桶过多了
     * @param nums 待处理数组
     * @return 最大间隙
     */
    public static int maximumGap1(int[] nums) {
        // 如果数组长度小于等于1直接返回0
        if (nums.length <= 1){
            return 0;
        }
        // 对nums进行桶排序
        bucketSort(nums, 1);
        // 排序结束后遍历nums数组求出最大的间隙
        int  maxGap = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            int gap = nums[i + 1] - nums[i];
            if (gap > maxGap){
                maxGap = gap;
            }
        }
        return maxGap;
    }

    /**
     * <h3>方法二：变种基数排序</h3>
     * @param nums 待处理数组
     * @return 最大间隙
     */
    public static int maximumGap2(int[] nums) {
        // 找出nums中的最大值
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
        }
        // 创建桶，数量是10，范围1
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>(10);
        // 初始化桶
        for (int i = 0; i < 10; i++) {
            bucketList.add(new ArrayList<>());
        }
        // 遍历nums，对nums的每一位进行基数排序，进行最大元素的位数这么多次基数排序
        int m = 1;
        int index = 0;
        while (m <= max){
            for (int num : nums) {
                bucketList.get(num / m % 10).add(num);
            }
            for (ArrayList<Integer> bucket : bucketList) {
                for (Integer i : bucket) {
                    nums[index++] = i;
                }
            }
            for (ArrayList<Integer> bucket : bucketList) {
                bucket.clear();
            }
            m *= 10;
            index = 0;
        }
        // 遍历nums找出最大间隙
        int maxGap = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxGap = Math.max(maxGap, nums[i + 1] - nums[i]);
        }
        return maxGap;
    }

    /**
     * <h3>方法三：改进方法一</h3>
     * @param nums 待处理数组
     * @return 最大间隙
     */
    public static int maximumGap3(int[] nums) {
        // 如果数组长度小于等于1直接返回0
        if (nums.length <= 1){
            return 0;
        }
        // 对nums进行桶排序
        int min = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > max){
                max = nums[i];
            }
            if (nums[i] < min){
                min = nums[i];
            }
        }
        // 期望桶的个数：nums.length
        // 实际桶的个数：(max - min) / range + 1
        // 那么(max - min) / range + 1 == nums.length
        // =>  range = (max - min) / (nums.length - 1)
        bucketSort(nums,Math.max((max - min) / (nums.length - 1), 1));
        // 排序结束后遍历nums数组求出最大的间隙
        int  maxGap = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            int gap = nums[i + 1] - nums[i];
            if (gap > maxGap){
                maxGap = gap;
            }
        }
        return maxGap;
    }

    /**
     * 桶排序
     * @param nums 待处理数组
     * @param range 桶的元素取值范围
     */
    private static void bucketSort(int[] nums, int range) {
        // 找出最大值、最小值
        int max = nums[0];
        int min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > max){
                max = nums[i];
            }
            if (nums[i] < min){
                min = nums[i];
            }
        }
        // 准备桶
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
        // 对每个桶进行初始化
        int capacity = (max - min) / range + 1;
        for (int i = 0; i < capacity; i++) {
            buckets.add(new ArrayList<>());
        }
        // 遍历nums数组，将数放入桶中
        for (int num : nums) {
            buckets.get((num - min) / range).add(num);
        }
        // 对每个桶进行排序
        for (ArrayList<Integer> bucket : buckets) {
            Collections.sort(bucket);
        }
        // 将排序后的桶合并更新nums数组
        int index = 0;
        for (ArrayList<Integer> bucket : buckets) {
            for (Integer i : bucket) {
                nums[index++] = i;
            }
        }
    }
}
